Работы в области генетических алгоритмов и генетического программирования публикуются в журналах Evolutionary Computation и IEEE Transactions on Evolutionary Computation', статьи на эти темы можно также найти в журналах Complex Systems, Adaptive Behavior и Artificial Life. Основными конференциями являются International Conference on Genetic Algorithms и Conference on Genetic Programming, а недавно произошло их слияние и создана конференция Genetic and Evolutionary Computation Conference. Хорошие обзоры этой области приведены в книгах Мелани Митчелл [1059] и Дэвида Фогеля [475].

Алгоритмы исследования неизвестных пространств состояний привлекали интерес ученых в течение многих столетий. Поиск в глубину в лабиринте можно осуществить, постоянно держась левой рукой за стену; циклов можно избежать, отмечая каждую развилку. При наличии необратимых действий поиск в глубину оканчивается неудачей; более общая задача исследования графов Эйлера (т.е. графов, в которых каждый узел имеет одинаковое число входящих и исходящих ребер) была решена с помощью алгоритма, предложенного Хирхольцером [652]. Первое исчерпывающее описание алгоритмов решения задачи исследования для произвольных графов было приведено в [385]; авторы этой работы предложили полностью общий алгоритм, но показали, что невозможно определить ограниченный коэффициент конкурентоспособности для задачи исследования графа общего вида. В [1171] приведены результаты исследования проблемы поиска путей к цели в геометрических вариантах среды планирования пути (где все действия являются обратимыми). Эти результаты показали, что достичь того, чтобы коэффициент конкурентоспособности оставался небольшим, можно при наличии квадратных препятствий, но если препятствия имеют произвольную прямоугольную форму, то невозможно добиться того, чтобы значения коэффициента конкурентоспособности оставались ограниченными (см. рис. 4.13).

Алгоритм LRTA* был разработан Корфом [839] в ходе исследований в области поиска в реальном времени для вариантов среды, в которых агент должен действовать после проведения поиска лишь в течение ограниченного времени (эта ситуация встречается гораздо чаще в играх с двумя участниками). По сути, алгоритм LRTA* представляет собой частный случай алгоритмов обучения с подкреплением для стохастических вариантов среды [74]. Применяемый в нем принцип оптимистического отношения к неопределенности (согласно которому следует всегда отправляться к ближайшему непосещенному состоянию) может в случае отсутствия информации о среде привести к формированию такого подхода к исследованию, который является менее эффективным по сравнению с простым поиском в глубину [818]. В [327] показано, что поиск с итеративным углублением в оперативном режиме обладает оптимальной эффективностью поиска цели в однородном дереве при отсутствии эвристической информации. В сочетании с различными методами поиска и обновления в известной части графа было разработано несколько вариантов алгоритма LRTA*, предусматривающих использование информации о среде [1201]. Тем не менее еще нет полного понимания того, как следует находить цели с оптимальной эффективностью при использовании эвристической информации.

Тема алгоритмов параллельного поиска в этой главе не рассматривалась, отчасти потому, что для этого требуется привести подробное описание параллельных компьютерных архитектур. Параллельный поиск становится важной темой и в искусственном интеллекте, и в теоретических компьютерных науках. Краткое введение в тематику литературы по искусственному интеллекту можно найти в книге Ма-ханти и Дэниелса [969].